GATE CSE 1999
Q1.
Arrange the following configuration for CPU in decreasing order of operating speeds: Hard wired control, Vertical microprogramming, Horizontal microprogramming.Q2.
A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor? a) Pointers b) Arrays c) Records d) Recursive procedures with local variablesQ3.
Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case isQ5.
If T_1 = O(1), give the correct matching for the following pairs: \begin{array}{l|l}\hline \text{(M) $T_n = T_{n-1} + n$} & \text{(U) $T_n = O(n)$} \\\hline \text{(N) $T_n = T_{n/2} + n$} & \text{(V) $T_n = O(n \log n)$} \\\hline \text{(O) $T_n = T_{n/2} + n \log n$} & \text{(W) $T_n = O(n^2)$} \\\hline \text{(P) $T_n = T_{n-1} + \log n$} & \text{(X) $T_n = O(\log^2 n)$} \\\hline \end{array}Q6.
The number of binary strings of n zeros and k ones in which no two ones are adjacent isQ8.
If L1 is context free language and L2 is a regular language which of the following is/are false?Q9.
Given the programming constructs I. assignment II. for loops where the loop parameter cannot be changed within the loop III. if-then-else IV. forward go to V. arbitrary go to VI. non-recursive procedure call VII. recursive procedure/function call VIII. repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming languageQ10.
If n is a power of 2, then the minimum number of multiplications needed to compute a^n is